package day04

// day04
//
// 474. 一和零
//
// https://leetcode.cn/problems/ones-and-zeroes/
//
// ```go
func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i < len(strs); i++ {
		zero, one := 0, 0
		for _, v := range strs[i] {
			if v == '0' {
				zero++
			}
		}
		one = len(strs[i]) - zero
		for x := m; x >= zero; x-- {
			for y := n; y >= one; y-- {
				dp[x][y] = max(dp[x][y], dp[x-zero][y-one]+1)
			}
		}
	}
	return dp[m][n]
}

//```

// 518. 零钱兑换 II
//
// https://leetcode.cn/problems/coin-change-ii/
//
// ```go
func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for i := 0; i < len(coins); i++ {
		for j := coins[i]; j <= amount; j++ {
			dp[j] += dp[j-coins[i]]
		}
	}
	return dp[amount]
}

//```
